package com.lry.basic.algorithm.dp;

/**
 * @author:刘仁有
 * @desc:
 * @email:953506233@qq.com
 * @data:2019/6/24
 */
//最长回文串
//input babad
//output bab或者aba
public class LongestPalindrome {
    //dp[i][j]表示从i到j是否是回文
    public static void main(String[] args) {
        String str ="222020221";
        System.out.println(new LongestPalindrome().longestPalindrome1(str));
    }

    public String longestPalindrome(String str) {
        if(null==str||str.equals(""))return "";
        int len = str.length();
        boolean[][] dp = new boolean[len][len];
        int start=0,max=0;
        for(int j=0;j<len;j++){
            for(int i=0;i<=j;i++){
                if(j-i<=1){//相邻或i=j
                    dp[i][j] = (str.charAt(i)==str.charAt(j));
                }else{//j-i>=2
                    dp[i][j] = (str.charAt(i)==str.charAt(j))&&dp[i+1][j-1];
                }

                if(dp[i][j]){
                    if(j-i>=max){
                        start=i;
                        max=j-i+1;
                    }
                }
            }
        }
        return str.substring(start, start+max);
    }


    public String longestPalindrome1(String s) {
        int len = s.length();
        boolean[][] dp = new boolean[len][len];

        int max = 0;
        int start = 0;

        for(int j=0;j<len;j++){
            for(int i=0;i<=j;i++){
                if(j-i<=1){
                    dp[i][j] = s.charAt(i)==s.charAt(j);
                }else{
                    dp[i][j] = dp[i+1][j-1] && s.charAt(i)==s.charAt(j);
                }

                if(dp[i][j]){
                    if(j-i+1>max){
                        start = i;
                        max = j-i+1;
                    }
                }
            }
        }

        return s.substring(start,start+max);
    }

}
